package com.ayuer.chapter10;


import java.util.List;
import java.util.PriorityQueue;

/**
 * 分数背包问题
 */
public class FractionBackpackAlgoDemo {

    public static class Goods {
        int index;
        int weight;
        int value;

        public Goods(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        public int unitValue() {
            return value / weight;
        }

        @Override
        public String toString() {
            return "Goods{" +
                    "index=" + index +
                    ", weight=" + weight +
                    ", value=" + value +
                    '}';
        }
    }

    public static void main(String[] args) {
        Goods[] goods = new Goods[]{
                new Goods(0, 4, 24),
                new Goods(1, 8, 160),
                new Goods(2, 2, 4000),
                new Goods(3, 1, 4000),
        };
        //给的背包大小为10
        int backpackSize = 10;
        int maxValue = 0;
        PriorityQueue<Goods> queue = new PriorityQueue<>((o1, o2) -> o2.unitValue() - o1.unitValue());
        queue.addAll(List.of(goods));
        System.out.println(queue);
        while (backpackSize > 0) {
            Goods good = queue.poll();
            assert good != null;
            if (good.weight < backpackSize) {
                //选择
                System.out.println(good);
                backpackSize -= good.weight;
                maxValue += good.value;
            } else {
                //分数
                maxValue += good.unitValue() * backpackSize;
                break;
            }
        }
        System.out.println(maxValue);

    }

}
